package com.dragon.datastructure.linkedlist;

/**
 * 反转一个单链表。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * <p>
 * <p>
 * 思路分析:
 *
 * @author dragon
 * @since 2019/12/17
 */
public class Test3 {

    private static class Node {
        Node next;
        int val;
    }

    public static Node reverse(Node head) {
        Node pre = null;
        Node cur = head;
        while (cur != null) {
            Node nextIterNode = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextIterNode;
        }

        return pre;
    }

    public static Node reverseList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node p = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return p;

    }
}
